package com.tgy.algorithm.base;

import java.util.Arrays;

public class _插入排序 {

    public static void insertSort(int[] nums) {

        if (nums == null || nums.length < 2) {
            return;
        }

        int j;
        // 3,2,2,4,6,1,5
        for (int i = 1; i < nums.length; i++) {

            // 找到当前元素最右的位置
            for (j = i - 1; j >= 0; j--) {
                if (nums[j] <= nums[i]) {
                    break;
                }
            }
            if (j + 1 != i) {
                int tmp = nums[i];
                for (int k = i; k > j + 1; k--) {
                    nums[k] = nums[k - 1];
                }
                nums[j + 1] = tmp;
            }
        }

    }

    public static void main(String[] args) {
        int[] ints = {3, 2, 2, 4, 6, 1, 5};
        insertSort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
